//测试——图算法
//编译：g++ TestGraphAlgo.cpp ../../*/*/Graph.hpp -o test
#ifndef __TESTGRAPHALGO__CPP
#define __TESTGRAPHALGO__CPP

#include<iostream>
#include<cstdlib>
#include<ctime>
#include"../../DataStructure/Graph/Graph.hpp"

using namespace std;
using namespace NgSiuKei;

void printGraphType(GraphType type) {
    cout << "边类型：";
    switch(type) {
        case GraphTypeUndirectedAndUnweighted: {
            cout << "无向无权图" << endl;
            break;
        }
        case GraphTypeUndirectedAndWeighted: {
            cout << "无向有权图" << endl;
            break;
        }
        case GraphTypeDirectedAndUnweighted: {
            cout << "有向无权图" << endl;
            break;
        }
        case GraphTypeDirectedAndWeighted: {
            cout << "有向有权图" << endl;
            break;
        }
        default: {
            break;
        }
    }
}

void printShortestPath(pair<DynamicStack<int>*, int> road) {
    if(!road.first->isEmpty()) {
        cout << "最短路径：[ ";
        while(!road.first->isEmpty()) {
            cout << road.first->pop() << " ";
        }
        cout << ']' << endl << "权重：" << road.second << endl;
    }
    else {
        cout << "无" << endl;
    }
}

void testGetShortestPathsInUnweightedGraph(void) {
    Graph<int, int> graph;
    const int size = 5;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    graph.setEdge(1, 2, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(1, 4, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(1, 5, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(3, 4, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(4, 5, Unweighted, GraphRoadTypeUndirected);

    printGraphType(graph.getType());
    pair<DynamicStack<int>*, int> road = graph.getShortestPaths(1, 3);
    printShortestPath(road);
    delete road.first;
}

void testGetShortestPathsInWeightedGraph(void) {
    Graph<int, int> graph;
    const int size = 5;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    graph.setEdge(1, 2, 5, GraphRoadTypeUndirected);
    graph.setEdge(1, 4, 4, GraphRoadTypeUndirected);
    graph.setEdge(1, 5, 10, GraphRoadTypeUndirected);
    graph.setEdge(3, 4, 2, GraphRoadTypeUndirected);
    graph.setEdge(4, 5, 3, GraphRoadTypeUndirected);

    printGraphType(graph.getType());
    pair<DynamicStack<int>*, int> road = graph.getShortestPaths(1, 5);
    printShortestPath(road);
    delete road.first;
}

void testIsConnectivity(void) {
    Graph<int, int> graph;
    const int size = 5;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    //非连通
    graph.setEdge(1, 2, Unweighted, GraphRoadTypeDirected);
    graph.setEdge(1, 4, Unweighted, GraphRoadTypeDirected);
    graph.setEdge(3, 4, Unweighted, GraphRoadTypeDirected);
    graph.setEdge(4, 5, Unweighted, GraphRoadTypeDirected);
    graph.setEdge(5, 1, Unweighted, GraphRoadTypeDirected);

    //连通
    // graph.setEdge(1, 2, Unweighted, GraphRoadTypeUndirected);
    // graph.setEdge(1, 4, Unweighted, GraphRoadTypeUndirected);
    // graph.setEdge(3, 4, Unweighted, GraphRoadTypeUndirected);
    // graph.setEdge(4, 5, Unweighted, GraphRoadTypeUndirected);
    // graph.setEdge(5, 1, Unweighted, GraphRoadTypeUndirected);

    cout << ((graph.isConnectivity())?("连通图"):("非连通图")) << endl;
}

void testHaveCycle(void) {
    Graph<int, int> graph;
    const int size = 5;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    graph.setEdge(1, 2, Unweighted, GraphRoadTypeDirected);
    graph.setEdge(1, 4, Unweighted, GraphRoadTypeDirected);
    graph.setEdge(3, 4, Unweighted, GraphRoadTypeDirected);
    graph.setEdge(4, 5, Unweighted, GraphRoadTypeDirected);
    graph.setEdge(5, 1, Unweighted, GraphRoadTypeDirected);
    // graph.setEdge(1, 5, Unweighted, GraphRoadTypeDirected);

    cout << (graph.haveCycle()?("有回路"):("无回路")) << endl;
}

void testGetMinSpanningTree(void) {
    Graph<int, int> graph;
    const int size = 5;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    //无向无权
    graph.setEdge(1, 2, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(1, 4, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(1, 5, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(3, 4, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(4, 5, Unweighted, GraphRoadTypeUndirected);

    //无向有权
    // graph.setEdge(1, 2, 5, GraphRoadTypeUndirected);
    // graph.setEdge(1, 4, 4, GraphRoadTypeUndirected);
    // graph.setEdge(1, 5, 10, GraphRoadTypeUndirected);
    // graph.setEdge(3, 4, 2, GraphRoadTypeUndirected);
    // graph.setEdge(4, 5, 3, GraphRoadTypeUndirected);

    printGraphType(graph.getType());
    GetMinSpanningTreeFuncType type = GetMinSpanningTreeFuncTypePrim;
    type = GetMinSpanningTreeFuncTypeKruskal;
    tree_node<int> *tree = graph.getMinSpanningTree(1, type);

    U_L_L num = getTreeNodeNum(tree);
    U_L_L height = getTreeHeight(tree);
    cout << "num = " << num << endl;
    cout << "height = " << height << endl;

    int *dfsArray = dfsOrderTree(tree);
    int *bfsArray = bfsOrderTree(tree);

    cout << "DFS = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << dfsArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "BFS = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << bfsArray[i] << ' ';
    }
    cout << ']' << endl;

    clearTree(tree);
    delete dfsArray;
    delete bfsArray;
}

void testGetMaximunFlow(void) {
    Graph<int, int> graph;
    const int size = 6;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    //无向无权
    graph.setEdge(1, 2, 10, GraphRoadTypeDirected);
    graph.setEdge(1, 3, 10, GraphRoadTypeDirected);
    graph.setEdge(2, 3, 2, GraphRoadTypeDirected);
    graph.setEdge(2, 4, 4, GraphRoadTypeDirected);
    graph.setEdge(2, 5, 8, GraphRoadTypeDirected);
    graph.setEdge(3, 5, 9, GraphRoadTypeDirected);
    graph.setEdge(5, 4, 6, GraphRoadTypeDirected);
    graph.setEdge(4, 6, 10, GraphRoadTypeDirected);
    graph.setEdge(5, 6, 10, GraphRoadTypeDirected);

    cout << "[Normal] 最大流量：" << graph.getMaximunFlow(1, 6, GetMaximunFlowFuncTypeNormal) << endl;
    cout << "[Ford-Fulkerson] 最大流量：" << graph.getMaximunFlow(1, 6, GetMaximunFlowFuncTypeFordFulkerson) << endl;
    cout << "[Edmonds-Karp] 最大流量：" << graph.getMaximunFlow(1, 6, GetMaximunFlowTypeEdmondsKarp) << endl;
    cout << "[Dinic] 最大流量：" << graph.getMaximunFlow(1, 6, GetMaximunFlowTypeDinic) << endl;
}

void testMinCut(void) {
    Graph<int, int> graph;
    const int size = 6;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    //无向无权
    graph.setEdge(1, 2, 10, GraphRoadTypeDirected);
    graph.setEdge(1, 3, 10, GraphRoadTypeDirected);
    graph.setEdge(2, 3, 2, GraphRoadTypeDirected);
    graph.setEdge(2, 4, 4, GraphRoadTypeDirected);
    graph.setEdge(2, 5, 8, GraphRoadTypeDirected);
    graph.setEdge(3, 5, 9, GraphRoadTypeDirected);
    graph.setEdge(5, 4, 6, GraphRoadTypeDirected);
    graph.setEdge(4, 6, 10, GraphRoadTypeDirected);
    graph.setEdge(5, 6, 10, GraphRoadTypeDirected);

    tuple<PriorityQueue<int> *, PriorityQueue<int> *, int> result = graph.getMinCut(1, 6);
    PriorityQueue<int> *S = get<0>(result);
    PriorityQueue<int> *T = get<1>(result);
    int weights = get<2>(result);

    cout << "S:" << endl;
    S->print();
    cout << "T:" << endl;
    T->print();
    cout << "最小割值：" << weights << endl;

    delete S;
    delete T;
}

void testBipartiteGraph(void) {
    Graph<int, int> graph1, graph2;
    const int size = 6;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph1.insertVal(i+1);
        graph2.insertVal(i+1);
    }

    //是
    graph1.setEdge(1, 2, Unweighted, GraphRoadTypeUndirected);
    graph1.setEdge(2, 3, Unweighted, GraphRoadTypeUndirected);
    graph1.setEdge(3, 4, Unweighted, GraphRoadTypeUndirected);
    graph1.setEdge(4, 5, Unweighted, GraphRoadTypeUndirected);
    graph1.setEdge(5, 6, Unweighted, GraphRoadTypeUndirected);
    graph1.setEdge(6, 1, Unweighted, GraphRoadTypeUndirected);
    // graph1.print();

    //不是
    graph2.setEdge(1, 2, Unweighted, GraphRoadTypeUndirected);
    graph2.setEdge(2, 3, Unweighted, GraphRoadTypeUndirected);
    graph2.setEdge(3, 4, Unweighted, GraphRoadTypeUndirected);
    graph2.setEdge(4, 5, Unweighted, GraphRoadTypeUndirected);
    graph2.setEdge(5, 6, Unweighted, GraphRoadTypeUndirected);
    graph2.setEdge(6, 1, Unweighted, GraphRoadTypeUndirected);
    graph2.setEdge(6, 4, Unweighted, GraphRoadTypeUndirected);
    // graph2.print();

    cout << "G1" << (graph1.isBipartite()?"是":"不是") << "二部图" << endl;
    cout << "G2" << (graph2.isBipartite()?"是":"不是") << "二部图" << endl;
}

void testGetMaxMatchingInUn(void) {
    Graph<int, int> graph;
    const int size = 10;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    int *U = new int[5];
    int *V = new int[5];
    for(i=0; i<5; ++i) {
        U[i] = i+1;
        V[i] = i+6;
    }

    graph.setEdge(1, 7, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(1, 8, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(2, 7, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(2, 8, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(2, 9, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(3, 6, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(3, 7, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(3, 8, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(3, 10, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(4, 8, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(5, 8, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(5, 9, Unweighted, GraphRoadTypeUndirected);
    graph.setEdge(5, 10, Unweighted, GraphRoadTypeUndirected);

    cout << "无权图最大匹配值：" << graph.getMaxMatching(U, 5, V, 5) << endl;

    delete []U;
    delete []V;
}

void testGetMaxMatchingInHungarian(void) {
    Graph<int, int> graph;
    const int size = 7;
    U_L_L i;
    for(i=0; i<size; ++i) {
        graph.insertVal(i+1);
    }

    int *U = new int[3];
    int *V = new int[4];
    for(i=0; i<3; ++i) {
        U[i] = i+1;
        V[i] = i+4;
    }
    V[3] = 7;

    graph.setEdge(1, 4, 8, GraphRoadTypeUndirected);
    graph.setEdge(1, 5, 25, GraphRoadTypeUndirected);
    graph.setEdge(1, 6, 50, GraphRoadTypeUndirected);

    graph.setEdge(2, 4, 50, GraphRoadTypeUndirected);
    graph.setEdge(2, 5, 35, GraphRoadTypeUndirected);
    graph.setEdge(2, 6, 75, GraphRoadTypeUndirected);

    graph.setEdge(3, 4, 22, GraphRoadTypeUndirected);
    graph.setEdge(3, 5, 48, GraphRoadTypeUndirected);
    graph.setEdge(3, 6, 150, GraphRoadTypeUndirected);
    graph.setEdge(3, 7, 8, GraphRoadTypeUndirected);

    cout << "有权图最大匹配值[匈牙利算法]：" << graph.getMaxMatching(U, 3, V, 4) << endl;

    delete []U;
    delete []V;
}

void testGetStableMarriage(void) {
    Graph<int, int> graph;

    //不需要入参和图相关
    int mans[4] = {1, 2, 3, 4};
    int womans[4] = {5, 6, 7, 8};
    
    LinkedQueue<int> mansLike[4];
    mansLike[0].push(5);
    mansLike[0].push(8);
    mansLike[0].push(7);
    mansLike[0].push(6);
    mansLike[1].push(5);
    mansLike[1].push(6);
    mansLike[1].push(7);
    mansLike[1].push(8);
    mansLike[2].push(6);
    mansLike[2].push(8);
    mansLike[2].push(7);
    mansLike[2].push(8);
    mansLike[3].push(7);
    mansLike[3].push(5);
    mansLike[3].push(6);
    mansLike[3].push(8);
    
    StaticList<int> womansLike[4];
    womansLike[0].insertVal(3, 0);
    womansLike[0].insertVal(1, 1);
    womansLike[0].insertVal(2, 2);
    womansLike[0].insertVal(4, 3);
    womansLike[1].insertVal(1, 0);
    womansLike[1].insertVal(4, 1);
    womansLike[1].insertVal(3, 2);
    womansLike[1].insertVal(2, 3);
    womansLike[2].insertVal(2, 0);
    womansLike[2].insertVal(4, 1);
    womansLike[2].insertVal(3, 2);
    womansLike[2].insertVal(1, 3);
    womansLike[3].insertVal(4, 0);
    womansLike[3].insertVal(2, 1);
    womansLike[3].insertVal(1, 2);
    womansLike[3].insertVal(3, 3);

    LinkedQueue<pair<int, int>> *result = graph.getStableMarriage(mans, mansLike, 4, womans, womansLike, 4);
    result->print();

    delete result;
}

int main(void) {
    //无权图
    // testGetShortestPathsInUnweightedGraph();
    //有权图
    // testGetShortestPathsInWeightedGraph();
    //是否连通图
    // testIsConnectivity();
    //是否回路
    // testHaveCycle();
    //获取最小生成树
    // testGetMinSpanningTree();
    //获取最大流量
    // testGetMaximunFlow();
    //获取最小割
    // testMinCut();
    //二部图
    // testBipartiteGraph();
    //最大匹配（无权）
    // testGetMaxMatchingInUn();
    //最大匹配（有权：匈牙利）
    // testGetMaxMatchingInHungarian();
    //稳定婚配
    testGetStableMarriage();

    return 0;
}

#endif